Vol.78 MI Lecture Notes|九州大学 マス・フォア・インダストリ研究所 math 5acd7940c3b8c

M

ISSN2188−1200

編集 :

瀧澤重志・小林和博・佐藤憲一郎・斎藤努

  清水正明・間瀬正啓・藤澤克樹・神山直之

九州大学マス・フォア・インダストリ研究所

九州大学マス・フォア・インダストリ研究所

編

集 _:

瀧

澤

重

志

・

小

林

和

博

・

佐

藤

憲

一

郎

・

斎

藤

努

・

清

水

正

明

・

間

瀬

正

啓

・

藤

澤

克

樹

・

神

山

直

之

防災・避難計画の数理モデルの高度化と社会実装へ向けて

平成29年度 九州大学マス・フォア・インダストリ研究所 プロジェクト研究 研究集会(I)

防

災

・

避

難

計

画

の

数

理

モ

デ

ル

の

高

度

化

と

社

会

実

装

へ

向

け

平成29年度　九州大学マス・フォア・インダストリ研究所

プロジェクト研究　研究集会（I）

防災・避難計画の数理モデルの高度化と社会実装へ向けて

About MI Lecture Note Series

The Math-for-Industry (MI) Lecture Note Series is the successor to the COE Lecture

Notes, which were published for the 21st COE Program “Development of Dynamic

Mathematics with High Functionality,” sponsored by Japan’s Ministry of Education,

Culture, Sports, Science and Technology (MEXT) from 2003 to 2007. The MI

Lec-ture Note Series has published the notes of lecLec-tures organized under the following two

programs: “Training Program for Ph.D. and New Master’s Degree in Mathematics as

Required by Industry,” adopted as a Support Program for Improving Graduate School

Education by MEXT from 2007 to 2009; and “Education-and-Research Hub for

Mathematics-for-Industry,” adopted as a Global COE Program by MEXT from 2008 to

2012.

In accordance with the establishment of the Institute of Mathematics for Industry (IMI)

in April 2011 and the authorization of IMI’s Joint Research Center for Advanced and

Fundamental Mathematics-for-Industry as a MEXT Joint Usage / Research Center in

April 2013, hereafter the MI Lecture Notes Series will publish lecture notes and

pro-ceedings by worldwide researchers of MI to contribute to the development of MI.

October 2014

Yasuhide Fukumoto

Director

Äĝ

ģ§,ĕĉ"20ÍĠACIS†Á#fı$©ÒôľïÕ§,ĆĊĤïÕ§! #ï…

Ī§s3’ƒ|ÏÑ'/Å"ėˆÔ401.#>5!0ØIJTJ

Y^=†Á$ì»ìİ 0Ĥ—‰¸!íÊ0ĕĉ"20ØIJTJZ"š+

#BU^Z /1.#Ĝĭ{#ķ$ '/ì$!ļ%m$MHK]

<O\"€ij­5Z?YDS#fıĜĭĕĉ•nīð3é0cġ-/

cĒû!ĕĉ•n3÷Ï0ģ§Ĝĭ$QZG:B9^K! "€ĕĉARV[

AW^3€Ĕ0ì

13wıEOK895#ēď,>^@ZI6^=+

‚"ħ{3÷Ï!10#Ĝĭ+ĦđýĂË /İ!µ˜,

-/£ą!TJY^=#†ÁrđÔ40

#-!ϔ.Ĥ—‰¾p$¸"ĕĉ"|20ØIJTJZgfı3¸!IQ

1"|20İ!BU^Z#—‰#¦äã,+}*fı#™Î3Çî¢ec

Ē¢e#“Éo11"‡Ł3¡

'

5

Ĩ#Çî¢e·"-0¢e$

'

QZG:B9^KACIS#€å.µ˜+

}*¦Ž#ýr"Įń±.àĩ!1¦œ#_̱$ĕĉARV[AW^

3íÊQZG:B9^KACIS#€å.fı'#Éo!1cġØIJ•

n#5P\G$

Wang

±§sęŠlú#¦üg"Éo

Pedro

±$ěØ#

 ƒ#cßöĴīð#¦üg3¦êO\#5P\Gžĵû"qġĢ3ÉoĖĭ

±$tĵ•nīð3ï…Ī!ĞĽ•®ƒ•®0Ńæ(²ļ#Éo3¡

cĒ¢e$ĕĉzĸ³{3õÀ0ĕĉĺb#ĜvºĢ¬Ĥ±

CNN

3ı¦êO

\#ĕĉzĸ³{#Öùÿ÷±Ó±

﩯.#ï…Ī!cßĀğ„òARV[AW^

â~±

ģ§ı#ŒÃ5PY#rđĥȱ

ă¯

OS

#Ńæ(ģ§ífćń±!

ì"ā0+#

Ĥ—‰¾p$a!0áĬĜĭ,ĶÌ3į«h·wđ"‡Ł3¡ëĜĭ#TJ

Y^=ºĢ,¶pµè#yÂ,ĉ3u&ç›IJqÔ)+"Ĺ·#ºĢ3¹/ċ1

Ð!ØIJûġĢ#ičÚ3ó0’ƒĈ.1

Ĥp‡ŀ$`Ë#—‰¾p#Ûk3þ*+# 0

ñń

¿°

(

﩯ĶïuŸu—‰j

)

ÆĻ

łĐ

(

ƋIJjïuIJŸuĘ

)

¥ć

–cĿ

(

|ĆudïuŸu—‰j

)

¨ć

Ą

(

x´p¶NPX8L

)

Ý×

Üĩ

(

x´p¶ĊĶÞªÂ

—‰rđ=ZP

)

{Ù

ܑ

(

x´p¶ĊĶÞªÂ

—‰rđ=ZP

)

­Õúž

«ĊĬī

ĜêJKĎĆ|‰kcft´©

´©×šBC

ġÁ>ĔČ°™Xèĭ‚s‡X¼Ć—VϚÎöY¶PU

(9%2')1)273*%7,)1%7-'%03()03*-6%67)55)9)27-32%2(

9%'8%7-320%22-2+73:%5( 3'-%0140)1)27%7-32

čÊ?

Ď ± čĥ

A

± č¬

ßÚ?

I ę•Èôİ®ïá

­Õúž

ïá|…i

úš¨Í

"

,774:::-1-/<86,88%'.4)9)2769-):

F|‰g…€G

± čBĥC

ÓĖ

›šXŒÅ

Ýø»“

ħķúÿćªúžðþ˜ž§Ùm‹n@

DĚĭžÐO¹MTĔȂs‡VSX”īE

Ýø»“

-2#%2+%7-32%0,)2+82+"2-9)56-7<¾ĮùĶêµúž

D)7:35/5)6735%7-326',)(80-2+-2,81%2-7%5-%203+-67-'61%2%+)1)27E

± č¬

ÓĖ

Ýø»“

%5-67%2<()0%6%6%6)(53!,)$86)267-787))50-2$

D-564%')9%'8%7-32 75%7)+-)6E

ē»“ ě û

HÆĢı=üķØÉúÃÈĮúžúž’¸ž´©˜

D(<2%1-'75))2)7:35/ W[]ĔČ¡įÊ¢^ÀܗR]

Đăÿ–œXæĂĔČIJXěŸÒğE

HăāĀ=ä¥Ġ­Õúžúž’èĭžė

Ýø»“

ĕĦĨË!,)$86)267-787))50-2$

D 309-2+;75)1)0<%5+) 73',%67-'-;)(27)+)553+5%16-2%5%00)0

32-675-&87)()135<31487-2+29-5321)276E

ē»“ ě û

Hģ޷Ǡ̚Ï}ft‡õ´

Dċė D«Û_|†EX›ĒVϚÎöXÑ\òZE

HĈķ½Ô­Õúž~l>{e_>a‹olt†´©Ú

Dyt>‚wX‚z†r`W£R]áQLèĭ‚s‡VSX”īE

Ýø»“

ę²ĩúÃúžhax@s`_m‹n@

Dd@kc‹t}@l‚s‡W[]ĔČjƒˆ@j„‹íĸ—Xĉ¶E

ĝšXŒÅ

òàŽ‘G

üķØÉúÃÈĮúž¸ž´©˜

Üijĵđćªĭ˜úžĭ¸žĘ

¿Ĉ³Ĵ£ćž’úž¸ž´©˜

ÂĈą ÌšÏz@|…bu

ìçëĤčĮîÄÚ´©›Ēg‡@|

¢éë¯čĮîÄÚ´©›Ēg‡@|

Ĉķ½Ô­Õúž~l>{e_>a‹olt†´©Ú

大韓民国総領事館 総合図書館

福岡市博物館 百道中央公園

西南学院 小学校

西新パレス 西新パレス前

ガスト 新今川橋

明治通り

鉄空港線 西新駅

今川橋 防災センター

早良消防署

中華人民共和国 総領事館

百道浜橋 よかとぴ

あ通り

九州大学西新プラザ

平成29年度 九州大学IMI 共同利用・研究集会

（

Ⅰ

）

防災・避難計画の数理モデルの

高度化と社会実装へ向けて

Advancement of Mathematical Model of Disaster Prevention and

Evacuation Planning toward Social Implementation

招待講演者

:

場所 :

九州大学西新プラザ 大会議室AB

〒814-0002 福岡市早良区西新2-16-23

日時

:

2017

年

11

月

30

日（木）∼

12

月

1

日（金）

http://www.imi.kyushu-u.ac.jp/events/view/2180

I-Lin Wang

（National Cheng Kung University，国立台湾成功大学）

Maristany de las Casas, Pedro

（

The Zuse Institute Berlin: ZIB）

品野 勇治

（The Zuse Institute Berlin: ZIB）

柳澤 大地

（東京大学先端科学技術センター）

安福 健祐

（大阪大学サイバーメディアセンター）

組織委員

:

瀧澤 重志

（大阪市立大学工学研究科）

小林 和博

（東京理科大学理工学部）

佐藤 憲一郎

（関東学院大学工学研究科）

斎藤 努

（株式会社ビープラウド）

清水 正明

（株式会社日立製作所 研究開発グループ）

間瀬 正啓

（株式会社日立製作所 研究開発グループ）

藤澤 克樹

（九州大学マス・フォア・インダストリ研究所）

神山 直之

（九州大学マス・フォア・インダストリ研究所）

九州大学IMI 共同利用・平成29年度プロジェクト研究

Table of Contents

|eE

¤¯Oqc¡8+<F®

«´

Ž’˜ZŽO†‘IOXx%@&

Network restoration scheduling in humanitarian logistics management

I-Lin Wang

National Cheng Kung University, Tainan City, Taiwan

Airspace Evacuation Strategies

Maristany de las Casas, Pedro

The Zuse Institute Berlin: ZIB, Berlin, Germany

Solving Extremely Large Stochastic Mixed-Integer Programs in Parallel

on Distributed Memory Computing Environments

Yuji Shinano

The Zuse Institute Berlin: ZIB, Berlin, Germany

#@,4$8+<¡"69=":@…µHš`

A£

^¬ŽhŽO!/7+%@&

C eE

dynamic tree network

¡R±mSg{Hž–’GM

ƒ•¡³B¥Ps§

i©

²Žhk°ŽOŽODbO_YI

joint work with ´wl

€‰Ov-),? 2>® ¡]JŒ3>(

–”

“\uŽOŽOD„¯O¢

joint work with V¨ (›~), ™´ ft(\uŽO5$2@'$,;_Yy)

ŽhkŽ’‚m—¦Wdš"69=":@

‡U

­Žhk°ŽOŽODbO_YI

joint work with ´wl (›~)

œN¢

SIP

[z3;LŸpKo‹rˆ

ª}

ajQnKp4 ,<Š_

0,8.81;*T „¯8+<F®

・・・・・・・・・・・・・・・・・・・　1

・・・・・・　19

・・・・・・・・・・・・・・・・・・・・・・　28

・・・・・・・・・・・・・・・　48

・・・・・・・・　67

・・・・・・・・・・・・・・・・・・・・・・・・・　97

・・・・・・・　107

・・・・・・・・・・・・　114

・・・・・・・・・・・・・　125

Advancement of mathematical model of disaster prevention and evacuation

planning toward social implementation

November 30-December 1, 2017, Fukuoka, JAPAN

෺ཧֶऀ͕ߟ͑ͨආ೉ϞσϧͱͦͷԠ༻

༄ᖒ

େ஍

౦ژେֶઌ୺Պֶٕज़ηϯλʔ

≀⌮Ꮫ⪅䛜⪃䛘䛯㑊㞴䝰䝕䝹䛸

䛭䛾ᛂ⏝

z

≀⌮Ꮫ⪅䛜⪃䛘䛯䝰䝕䝹

z

Social Force Model

z

Totally Asymmetric Simple

Exclusion Process (TASEP)

(1D Cellular Automaton)

z

Floor Field Model

z

ᛂ⏝౛

z

ὶືಀᩘ䛸㞀ᐖ≀

z

᤼௚ᚅ䛱⾜ิ

z

Ṍ⾜㊥㞳䜢ᑟධ䛧䛯ᚅ䛱⾜ิ

z

㐜䛔䝸䝈䝮䛻ྜ䜟䛫䛯Ṍ⾜

ᰗ⃝኱ᆅ

@

ᮾ኱

ඛ➃◊

◊✲䝔䞊䝬

• ⩌㞟㐠ື

• 䝉䝹䜸䞊䝖䝬䝖䞁䠄䛾ᛂ⏝䠅

• ᚅ䛱⾜ิ⌮ㄽ䠄䛾ᛂ⏝䠅

ᵝ䚻䛺⩌㞟㐠ື䛸◊✲ศ㔝

኱⩌㞟

㏥ฟ

཮᪉ྥὶ

ᚅ䛱⾜ิ

┠ᶆ䠖Ᏻ඲ᛶ䛾ྥୖ䛸䝇䝖䝺䝇䛾㍍ῶ

䠘ᩘᏛ䞉≀⌮䛻䜘䜛⩌㞟㐠ື䛾◊✲䠄

2000

ᖺ䡚䠅䠚

‹

䝰䝕䝹䛾୍⯡໬䚸๰Ⓨ⌧㇟䛺䛹䛾ㄝ᫂䚸⌮ㄽゎᯒ

‹

ே䜢⮬ᕫ㥑ື⢏Ꮚ䛸䛧䛶ᢅ䛖

⯆࿡῝䛔⌧㇟䜢฼⏝䛧䛶ΰ㞧ゎᾘ䜢┠ᣦ䛩䟿

⯆࿡῝

⌧㇟䜢฼⏝

ΰ㞧ゎᾘ䜢┠ᣦ䛩

⩌㞟㐠ື䛾ᩘ⌮≀⌮ⓗ䝰䝕䝹

䝰䝕䝹

1..

䝬䜽䝻

䠄ὶయ䝰䝕䝹䠅

2.

2.

䝭䜽䝻

㐃⥆✵㛫

㐃⥆

⥆

㛫

(Social Force Model)

3.

3.

䝭䜽䝻

㞳ᩓ✵㛫

㞳ᩓ

㛫

䠄䝉䝹䜸䞊䝖䝬䝖䞁䠅

ே

㐃⥆య

⢏Ꮚ

⢏Ꮚ

✵㛫

㐃⥆

㐃⥆

㞳ᩓ

䝎䜲䝘䝭䜽䝇 ὶయ䛾ᚤศ᪉⛬ᘧ

㐠ື᪉⛬ᘧ

䝹䞊䝹

ᑐྥὶ

䛾

ᶍᘧᅗ

䠄┿䜣୰䛷

䖃 䖃 䖃

䖃 䖃 䖃

䖃 䖃 䖃

䖃 䖃 䖃

䖃 䖃 䖃

䖃 䖃 䖃

䖃 䖃 䖃

䖃 䖃 䖃

䖃 䖃 䖃

Social Force Model

0

_{( ) ( )}

0

_{( )}

i i i i

i i ij iW

j i W

i

d

v

t

t

t

m

m

f

f

dt

W

_z

¦ ¦

v

e

v

Acceleration

Desired Velocity

Reaction Time

Interaction Force from

other pedestrians

Interaction Force from

walls and obstacles

Exit

䠍ḟඖ☜⋡䝉䝹䜸䞊䝖䝬䝖䞁

䠄㠀ᑐ⛠༢⣧᤼௚㐣⛬

TASEP

䠅

•

☜⋡

䛷ྑ㞄䛾䝉䝹䛻⛣ື䛧䛶䛔䛟

•

ྑ㞄䛾䝉䝹䛻ู䛾⢏Ꮚ䛜䛔䛯䜙⛣ື䛷䛝䛺䛔

•

ୖᅗ䛿䚸࿘ᮇቃ⏺

A

B

C

D

A

B

C

D

D

B

C

+ 1

+ 2

A

Ṕྐ䛸ᛂ⏝౛

䞉

Protein composition

process of Ribosomes on

mRNA (1968)

䞉

Bursting of housing bubble

䞉

Matrix-products ansatz,

Bethe ansatz

䛻䜘䜛ཝᐦゎ

(1990

ᖺ௦

)

῰䜽䝷䝇䝍䞊䛾ᚋ᪉䜈䛾⛣ື䛾෌⌧

‹

ᴟ䜑䛶䝅䞁䝥䝹䛺䝰䝕䝹䛻䜒㛵䜟䜙䛪䚸

῰䜽䝷䝇䝍䞊䛜ᚋ᪉䛻⛣ື䛧䛶䛔䛟

ᛶ㉁䜢෌⌧ྍ⬟䟿

‹

ᕥ➃䠍䚸ྑ➃䠌䛾㛤ᨺቃ⏺䠄➃䛿⧅䛜䛳䛶䛔䛺䛔䠅

‹

ඛ㢌䛾㌴䛜ῶ㏿䛧䛶䠎䝇䝔䝑䝥Ṇ䜎䛳䛶䛧䜎䛳䛯䛸䛝䞉䞉

⩌㞟㐠ື䜈䛾ᛂ⏝䠄䠍ḟඖ䠅

䠄ே䛜㐨䜢ᕥ䛛䜙ྑ䛻Ṍ䛔䛶⾜䛟䝰䝕䝹䠅

<

㛗ᡤ

>

„

䝹䞊䝹䝧䞊䝇

„

᤼㝖య✚ຠᯝ

„

☜⋡䛾ᑟධ

„

䝅䝭䝳䝺䞊䝅䝵䞁䛜ᐜ᫆

„

⌮ㄽィ⟬䛜ྍ⬟

<

▷ᡤ

>

„

⣽䛛䛔ື䛝䛜⾲⌧䛷䛝

䛺䛔

„

ᐃᛶⓗ䛺ᛶ㉁䞉ᨵၿ⟇

䜢䝅䞁䝥䝹䛻ㄝ᫂䞉ᥦ᱌

2

1

E

0

1

2

1

2

O O O

䡌

䡌

䡌

䡌

䡌

Ĺ

2

2

5

5

5

5

2 2

2 2 1

2 2

Hopping probability

= exp

䞉

dir = , , , , stay

䞉

: Normalization

䞉

: Sensitivity parameter

䞉

: Static floor field

(Distance to the exit)

Only one pedestrian

Floor Field Cellular Automaton

Model for Evacuation

5

Dynamic Floor Field

D

D

D

D

D

is the number of footprints.

Pedestrians leave a footprint.

Pedestrians tend to move a

cell which contains large D.

D

D

D

diffuses and decays.

D

D

D

D

mimics the long-range

interaction by short-range one

.

exp

,

x s x d x

x

p

N

k S

k D

D



R

1

₍₁

₎₍₁

₎

(1

)

4

t t t

here here x

x here

D

D

G

D

D

G

D

z

¦

Basic Features of Collective

Behaviors of Pedestrians

‹

‹

Arch Formation at an Exit

‹

‹

Oscillation of Flow at

‹

Oscillation of F

O

a Bottleneck

‹

‹

Lane Formation of

‹

Lane Formatio

L

Counterflow

w

w at a corridor

atio

on of

Both the Social Force Model and the Floor Field Model

can reproduce these collective behaviours.

Advantage (Disadvantage) of

the Social Force Model and

the Floor Field Model

‹

‹

Advantage of the

g

e

Social Force Model

‹

Detailed Movement

‹

‹

Advantage

ge of the

e

Floor Field Model

‹

Exclusive Volume Effect

‹

Fast Calculation Time

ᛂ⏝

z

ὶືಀᩘ䛸㞀ᐖ≀

z

᤼௚ᚅ䛱⾜ิ

z

Ṍ⾜㊥㞳䜢ᑟධ䛧䛯

ᚅ䛱⾜ิ

z

㐜䛔䝸䝈䝮䛻ྜ䜟䛫䛯Ṍ⾜

ὶືಀᩘ䛸㞀ᐖ≀

Pedestrian Outflow and Obstacle

z

Phys. Rev. E, 76(6), 061117, 2007

z

Phys. Rev. E, 80(3), 036110, 2009

z

SICE Journal of Control, Measurement, and System Integration,

3(6), pp. 395-401, 2010

Pedestrian Outflow (POF)

‹

Pedestrian Outflow (POF) is the number of

pedestrians, who go through an 1 [m] exit in 1 [sec].

‹

POF greatly affects

g

g

[ ]

s Total Evacuation Time.

‹

Large POF = Small Total Evacuation Time.

‹

Motivation 1: How to estimate POF for various cases?

Time =

POF=

䠌

䠍

䠎

䠌

䠎

.

䠑

䠷

sec

䠹

䠷

persons/

䠄

m

䞉

sec

䠅䠹

Simulation

Exit

Important!

Does not

important

Mathematical Formulation for POF

‹

There are pedestrians

around the Exit cell.

‹

pedestrians are trying

to move to there.

‹

No cell structure (lattice).

( determines the cell

structure.)

E

1

2

k

E

E

E

1

E

1

E

,

=

1

+

1

1

POF:

= 1

= 1

Two Important Factors in Evacuation

through an Narrow Exit

2. Turningg

g

g

g

g

g

g

g

thro

1. Conflicts

= 1 1 1

0,1 : Aggressive parameter : Number of pedestrians move to an exit at the same time

= exp

0,1

0, : Inertia coefficient

o

t

= 1 1 11

Friction Function

0 1

Turning Function

g

g

g

g

g

g

g

Schematic View of the Experiments

(A) n=1 (B) n=2

(E) n=3

(G) n=4 (H) (I)

150 cm

6

S 2

S

0

4

S

(C) n=2 0

0 2

S

(D) n=2 S20 (F) n=3

2

S

6

S

150 cm ‹

Exit Width

50cm

‹

Evacuees

18 people

‹

2 or 3

times each

Theory v.s. Experiment

Zipper merging

(Almost 1 lane)

Quiz Which is the fastest?

1RUPDO

OLQH

6KLIWHG

2EVWDFOH

&HQWHU

2EVWDFOH

Effect of an Obstacle

<No Obstacle>

Model

<Shifted>

E

E

E

2.52

2.50

2.60

<Center>

ൾ౎ୄठষഔૌங

Exclusive Queueing Process

z

JSIAM Letters, 2, pp. 61-64, 2010

z

J. Stat. Phys., 141(5), pp. 829-847, 2010

N-Queue & E-Queue

<

N-Queue

>

(Normal Queue) (ConventionalModel)

<

E-Queue

>

(Exclusive Queue) (NewModel)

Service window

O

P

_D

_D

_CC

_BB

Service window

_A

_A

O

P

D

D

CC

BB

1

O

D

D

CC

BB

A

A

OP

OP

t

1

t

EE

D

D

CC

BB

EE

Number = 4 Length = 5

Number = 4 Number = 4 Length = 4 Number = 4

Length = 4

Number = 4 Length = 4

Balance Equations of E-Queue

(Master Equations in the Stationary State)

Number of pedestrians in a queue,

Length of a queue, and Waiting time

are

e

a queue, a

exactlyy

y

y

y

y

y

y

y

y

obtained.

>

@

0 0 0

(1 ) (1 ) (1,0),

(1,0) (1 )(1 ) (1,0) (1 ) (1,0),

( , ) (1 ) ( 1, ) (1 )(1 ) ( , 2 ) ( , 2 1) (Group A

A

A A B

A A A A

P P P

P P P P

P n m P n m P n m P n m

O

O P

O

O

P

O

O

P

O

P

2

2 2 2

2 1

1: 2, 0 2 1),

( , ) ( 1, 2 ) (1 ) ( , 2( 2 )) ( , 2( 2 ) 1)

(Group A2: 2, 2 2 1), ( , )

n

n n n

A B B B

n n

B A

n m

P n m P n m P n m P n m

n m

P n m P

O

O

OP

t d d

ª º

_{¬ ¼}

t d d

>

@

( , ) (1 ) ( 1, 2 ) ( 1, 2 1) (Group B: 1).

A A

n m P n m P n m

n

O P

t

Convergence Condition

N-Queue

E-Queue

N

Queue

+

C

/

E

Queue

+

P

/

Converge

Diverge

0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

0.6

0.8

1.0

O

P

Arrival Probability

Se

rv

ice

Pro

ba

bi

lit

y

E-Queue’s

condition is

severe because of the

severe because of thee

time for closing up

g

g

g

g

g

g

p

p

p

p

p

.

<

< 1

<

_{1 +}

<

Queue infinitely grows.

Stationary state exits.

Experiment

Service window 3 [m] 6 [m]

1. Arrives at

the queue.

3. Leave

the queue.

2. Proceeds in the queue.

Inter-arrival

time

1/

Service

1/

Name

Middle

䠄Fast arrival and service

Fast

䠅

15 [sec]

9.47 [sec]

5 [sec]

12 [sec]

7.58 [sec]

4 [sec]

Slow

䠄Slow arrival and service䠅

Arrival:

Service:

0.8

Slow Middle Fast

Slow

Middle

Fast

0 100 200 300 400 0 5 10 15 20 25 30

t

#

sec

'

n

#

pe

rs

on

s

'

Which Convergence Condition is

More Realistic?

1

O

P

_P

N-Queue

O

P

E-Queue

In Fast case,

0.2

0.2,

,

0.2

1

5

P

P

O

P

N-Queue’s

condition:

䕿

E-Queue’s

condition:

㽢

э

E-Queue

is more realistic!

< 1

Ṍ⾜㊥㞳䜢ᑟධ䛧䛯ᚅ䛱⾜ิ

Walking-Distance introduced

Queueing Model

z

Transportation Research Part C: Emerging Technologies,

In Press, DOI: 10.1016/j.trc.2013.04.008

1 2 3 4

C C C C C C

1 2 3 4

C C C C C C 2 a 2 b 2 k P P O p p 2 b P /s O O/s

p P /s O /s O p

<Fork>

Which type is more efficient?

<Parallel>

(ex. Checkout counters

in a supermarket

䠅

(ex. Automated teller

machines in a bank)

Service

Windows

=Waiting time is short.

Slow Middle Fast

Slow

Middle

Fast

0 100 200 300 400 0 5 10 15 20 25 30

Which Convergence Condition is

More Realistic?

1

O

P

_P

N-Queue

O

P

E-Queue

In Fast case,

0.2

0.2,

,

0.2

1

5

P

P

O

P

N-Queue’s

condition:

䕿

E-Queue’s

condition:

㽢

э

E-Queue

is more realistic!

0.0 0.2 0.4 0.6 0.8 1.0 0 1 2 3 4 5 6 7

Degree of Congestion

M ea nW ait in gT im e

N-Parallel

N-Fork

Conclusion from “Normal” Queueing Theory

N-Parallel

N-Fork

N-Fork

is better!

Quiz Which waiting time is shorter?

)RUN!

3DUDOOHO!

Distance to the window

ٛ

D-Fork

ٜ

(Distance introduced Fork)

(

1)

n

d

a

b

k n

1

n n

d

T

p

P

Waking time

Mean transit time to pass

the window

Mean transit rate to pass

the window

Service time

1 2 3 4

C C C C C

C

1 2 3 4

C C C C C

C

2

a

2

b

2

k

P

P

O

p

p

1

= + , =

㻨㻺㻙㻼㼍㼞㼍㼘㼘㼑㼘㻪

Balance Equations

0 1 1 1 1 1 1 1

( 1) ( ) (1 1) ( ) ( )

n n

s s

n n n

n n n

P P

P n P n P n s

P s P s P n s

O

O O

O

P

P P

P O P

d d t ࠉࠉ ࠉࠉࠉ

㻨㻺㻙㻲㼛㼞㼗㻪

㻨㻰㻙㻲㼛㼞㼗㻪

P

P

n

P

P

n

: Probability of

of

n

n

pedestrians are waiting.

Normal Model:

Ideal

model for pedestrian queues.

Distance Model:

Realistic

model for pedestrian queues.

0 1

1 1

1

1

(

1

)

(

1)

n n n

P

P

P

P

P

n

P

P

O

P

O

O

ࠉࠉ

t

0 1

1 1

(

)

(

1)

n n n

P

P

P

P

P

n

O

P

O

P

P

O

ࠉࠉ

t

0 1 1 1 1 1

( 1) ( ) (1 1)

( ) ( )

n n n

n n n

P P

P n P n P n s

P s P s P n s

O O O O O P P P P P d d t ࠉࠉ ࠉࠉ

㻨㻰㻙㻼㼍㼞㼍㼘㼘㼑㼘㻪

1 2 3 4

C C C C C C

1 2 3 4

C C C C C C 2 a 2 b 2 k P P O p p 2 b P /s O O/s

p P /s O /s O p

Arrival-service ratio

= /

Reversal of Mean Waiting Time

㻺㻙㻼㼍㼞㼍㻚

㻺㻙㻲㼛㼞㼗

㻰㻙㻼㼍㼞㼍㻚

㻰㻙㻲㼛㼞㼗

= 4

= 0.1

= 1

= 0.3

= 0.2

1

_Crossing

_ngg

_g

_g

_g

_g

_g

_g

䟿

Me

an

w

ai

tin

g

time

When the queueing system is congested

D-Parallel’s

becomes smaller than

D-Fork’s

!

Suitable Type of Queueing System

Ef fe ct o f w al ki ng d ist an ce

(A) Parallel

(D)

(E) Fork

(B)

(C)

=(walking time)_{(serivice time)} =_1//

D-Fork-Wait

There is no effect of

Walking Time

!

э

Waiting time may become small as that of

N-Fork

!

Experiment

( = 0.63,

= 0.38)

W W W W

Parallel

Fork

Fork-Wait

Parallel

Fork

Fork-Wait

Mean modified waiting time

㐜䛔䝸䝈䝮䛻ྜ䜟䛫䛯Ṍ⾜

Walking with Slow Rhythm

z

Phys. Rev. E, 85(1), 016111, 2012.

g

y

b

h

r

_i

r

_o

Walking on Music

Frederik Stynset al, Walking on Music, Human Movement Science, 26, 769, 2007.

Pace

v.s.

Velocity

Music Tempo

v.s.

Pace

Music Tempo

Ҹ

Pace

Velocity

҃

Pace

Rhythm can control walking velocity of single pedestrian.

What happens in a crowd case?

b

h

r

i

r

o

N

pedestrians

Circuit and Model

Assumptions

‹

Overtaking is prohibited.

‹

Both characteristics and distribution of pedestrians

are homogeneous.

Parameters

‹

Length of the circuit:

‹

Density

=

‹

Headway Distance

=

‹

=

Stride Function

S

and

Pace Function

P

StrideS

PaceP

0.0 0.2 0.4 0.6 0.8 1.0 0.0

0.5 1.0 1.5 2.0

DensityU

#

persons

s

m

'

St

rid

e

S,

Pa

ce

P

b=1,s=2,k=1,

p=1,a=0.2 ¨_©§ kbs b¸_¹·

k

j c

1 ,U U

c

U

j

U

Velocity

Stride

Pace

Low-density regime

‹

0,

‹

=

₌

High-density regime

‹

,

‹

₌

=

( )

_{( )}

=

( )

StrideS

PaceP

0.0 0.2 0.4 0.6 0.8 1.0 0.0

0.5 1.0 1.5 2.0

DensityU

#

persons

s

m

'

St rid e S, Pa ce P

Normal

and

Rhythmic

Walking

Normal Walking

a

>0

Pace

does not change in

the high-density regime.

StrideS

PaceP

0.0 0.2 0.4 0.6 0.8 1.0 0.0

0.5 1.0 1.5 2.0

DensityU

#

persons

s

m

'

St rid e S, Pa ce P

Pace

decreases in the

high-density regime.

Rhythmic Walking

a

=0

Density [person/m]

Density [person/m]

Theoretical Analysis

Fast Rhythm

Normal

Slow Rhythm

0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

0.6

0.8

Density

U

#

persons

s

m

'

Fl

ow

Q

#

pe

rs

on

s

s

se

c

'

(

p

,

a

)

(1.2, 0)

(1, 0.5)

(0.8, 0)

Fast Rhythm

increases the pedestrian flow.

Slow Rhythm

improves the flow in the high-density regime.

Convex

Downward

Density [person/m]

Fl

ow

[p

er

so

ns

/se

c]

Single Pedestrian Walking

with Rhythm

㻜 㻜 㻚㻡 㻝 㻝 㻚㻡 㻞 㻞 㻚㻡

㻡 㻜 㻝 㻜 㻜 㻝 㻡 㻜 㻞 㻜 㻜 㻞 㻡 㻜

㻮㻼㻹

㼂

㼑㼘

㼛

㼏㼕

㼠

㼥

㻌

㼇

㼙

㻛㼟

㼉

㻮㻼㻹 㻺㼛㼞㼙㼍㼘

Beet per Minutes (BPM)

Normal

Normal v.s. 70 BPM

(Number = 6, Density = 0.47 [1/m])

Normal

70 BPM

= 1.8 [m]

= 2.3 [m]

Normal v.s. 70 BPM

(Number = 24, Density = 1.86 [1/m])

Normal

70 BPM

= 1.8 [m]

= 2.3 [m]

Experimental and Theoretical Results

Crossingg

g

g

g

g

g

g

g

g

70 BPM

Conclusion

„

Pedestrian Outflow and Obstacle

Conflicts and Turning affects the pedestrian outflow.

Obstacle may improve pedestrian outflow.

„

Exclusive Queueing Process

Excluded-volume effect is important in pedestrian

queue.

„

Walking-Distance Introduced Queueing Model

Suitable type of queueing system changes according to

the arrival and service rates.

„

Walking with Slow Rhythm

Advancement of mathematical model of disaster prevention and evacuation

planning toward social implementation

November 30-December 1, 2017, Fukuoka, JAPAN

Network restoration scheduling in humanitarian

logistics management

I-Lin Wang

Underground Pipeline Network

Restoration Scheduling Problems

in

Post-disaster Humanitarian Logistics

by

16:05-17:05, Nov. 30, 2017 @ Meeting RoomAB Nishijin Plaza, Kyushu University

I-Lin Wang

Department of Industrial & Information Management National Cheng Kung University, Tainan, Taiwan

Advancement of mathematical model of disaster prevention and evacuation planning toward social implementation

8QGHUJURXQG3LSHOLQH1HWZRUNV

2

3LSHOLQH'DPDJHV

• Gas explosion at Kaohsiung

(Jul. 2014)

– 29,789 families no electricity

– 23,642 families no gas

– 13,500 families no water

– 2,780 families no phone line

–

> 3 months

to recover

• Earthquake at Tainan

(Feb. 2016)

– 117 casualties

:RUNVWR5HVWRUHD3LSHOLQH$UF

• A restoration team has to

– excavate

earth

– close

control valves

– repair

or

replace

pipeline

– backfill

earth

• Take

days

or even

weeks

– Worse for large-scale area

4

$UF5HVWRUDWLRQ3UREOHP

• Given

– A connected

network

with

damaged arcs

• w.l.o.g. assuming

all arcs

are damaged

– Demands

(D

ij

) &

restoration time

(P

ij

) for each arc (i,j)

– Source nodes

(accessible to outside flow)

– Restoration team

profile (capability, effectiveness)

• Assumption:

– Nonpreemptive

scheduling (no interruption)

– 1 team for 1 arc at 1 time

• Objective

– Minimize

total waiting time

5

Team

Time

Network compacting

5HVRXUFHG&RQVWUDLQHG3URMHFW

6FKHGXOLQJ3UREOHP5&363

•

7UHDWWKH

QHWZRUNUHVWRUDWLRQ

DVD

SURMHFW

–

$Q

DUFUHVWRUDWLRQ

DVD

WDVN

•

5HVRXUFHV

–

PDQSRZHU

EXGJHWHTXLSPHQWVNLOOHQHUJ\

•

6SHFLDO5&363ZLWK

QHWZRUN

VWUXFWXUH

•

1RFOHDU

SUHFHGHQFHUHODWLRQ

$Q,OOXVWUDWLYH([DPSOH

7 S C G H I J K L F E D A B

$Q,OOXVWUDWLYH([DPSOH

8 S C G H I J K L F E D A B XQGDPDJHGDUF GDPDJHGDUF GHPDQGUHVWRUDWLRQWLPH (5, 0) (3, 0) (2, 0) (4, 0) (7, 6) (4, 2) (3, 1) (8, 0)

(5, 0)

(4, 0) (7, 0) (8, 0) (6,5)

(8, 2) (2, 1) _{(1, 3)}

(3, 7) (4, 5)

LWLQFXUVXQLWVRIZDLWLQJWLPHIRU HYHU\GLVFRQQHFWHGGHPDQGXQLW

7KHVHGHPDQGV ǵǵǵǵ DUHVWLOOZDLWLQJQRZ

/LWHUDWXUH5HYLHZ

3UREOHP7\SH 5HIHUHQFH

0D[LPXP)ORZ .DOLQRZVNL HWDO

0LQFRVW)ORZ $YHUEDNK 0DWLV]LZ HWDO ;XHWDO &DYGDURJOX HWDO 6KRUWHVW3DWK %D[WHUHWDO

10

Ў᝘᏾౛

0XOWL

WHDPV 'HPDQGV6DWLVI\ 3UREOHP7\SH

1RGHRU $UF GHPDQG

$YHUEDNK _& 1RGH

$YHUEDNK DQG3HUHLUD 1RGH

.DOLQRZVNL HWDO 1 1RGH

%D[WHUHWDO 1 1RGH

0DWLV]LZ HWDO 1 & cost 1RGH

;X HWDO 1_& 1RGH

&DYGDURJOX HWDO 1RGH

1XUUH DQG6KDUNH\ _&, , 1RGH

2XU ZRUN $UF

General graph, k=1 Single PATH, general k

&KDOOHQJHV

•

0LQLPL]LQJ

WRWDOZHLJKWLQJWLPH

LVPRUHGLIILFXOW

EXWQHFHVVDU\

–

7LPHVSDFHQHWZRUN

H[SDQVLRQ

•

5&363LVDOUHDG\

13KDUG

–

:LWKJHQHUDO

QHWZRUNVWUXFWXUH

–

1RFOHDU

SUHFHGHQFHUHODWLRQV

•

0XOWLSOH

UHVWRUDWLRQWHDPV

–

3DUDOOHORSHUDWLRQV

11

How about single team?

outside

Î

inside

Arc Selection Intuition for

Single

Team

S C

G H

I

J

K

E D

A

B

(5, 3)

(3, 4) (2, 1) (4, 2)

(7, 6) (4, 2)

(3, 1) (8, 1)

(5, 1) (7, 1)

(8, 1) (6, 5)

(8, 2) (2, 1) _{(1, 3)}

(3, 7) (4, 5)

13 Min ( A (1 ))

a a a a A

D f M y



¦

0( ) (1 )

T A

a a at a t

f

¦

tP x M y a A

( ) 0 (1 )

T N at tail a a t

tx tf M y a A

¦

0( ) 1

T at at t

x x a A

¦

0

T a at

t

y

¦

x a A

(2) (1)

(3)

(4)

(5)

Integer Program for

Single

Team

( )

1

, 0 ( )

, , 1, ,

a

t P

it it at as

a A s

head ai

z z G x i N i S t T



d d _{¦ ¦}  z }

1 , 1, , it it

zdz i S t }T

( ), { ,a} , 0, , at head a min T t P

xdz a A t }T

0

1

T it t

zt i N

¦

1 1

( ) N (1 ( )) , 1, ,

it it i it it

t zz df d t M zz i N t }T

(7) (6) (8) (9) (10) 0 1 i

z i S

0 0 , i

z i N izS

{ a1,0} 0, , t

a as a A s max t P

R x R t T

 d }

¦ ¦

(12) (11)

(13)

Can

NOT

be extended for

Multi Teams

Arc Selection Intuition for Multi

Team

14 S C G H I J K L F E D A B (5, 3) (3, 4) (2, 1) (4, 2) (7, 6) (4, 2) (3, 1) (8, 1) (5, 1) (4, 1) (7, 1) (8, 1) (6, 5) (8, 2) (2, 1) _{(1, 3)}

(3, 7) (4, 5)

4

%HVLGHV

ERXQGDU\DUFV

ZKLFKRWKHUDUFWREHVHOHFWHG"

4

$IWHUDQDUFUHVWRUDWLRQ

+RZWRXSGDWHWKH

DUFDFFHVVLELOLW\

"

, 0 (1 ) 2 e p T a a t t a AA

D

Min x

 ‰

¦ ¦

, ,

, ( ) , ( ) 0 , 0, ,

e p e p

a t a t

a AA tail ai a AA head ai

x x i N t T

 ‰¦  ‰¦ 

, , , 0, ,

a t a t p

x dz a A t T

, , , 0, ,

a t a t p

z z a A t T

, , 1 0 1

a

T P R

a t r p

r t

s a A

d  ¦ ¦

min{ , 1}

, , 1 0, , , 1, , a

p T t P

a u r a A u t

t T r R

D

 d

¦ ¦

, , , ,

0( ) =0 , 1, ,

a

T P T

a a t r a t r p

t t

t P s tD a A r R



¦ ¦

, , , , ,

0 1( ) 0 , t 0, , t R

a t a u r a u r p

u r

z _¦¦D D d a A T

,0, 0 , 1, ,

ar a Apr R

D 

, , 1 0 1 RT

a t r p

r t

a A D

d 

¦¦ (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)

Integer Program for

Multi

Team based on

Multicommodity Flow

IP Modeling Intuition

16 S C G H I J K L F E D A B (5, 3) (3, 4) (2, 1) (4, 2) (7, 6) (4, 2) (3, 1) (8, 1) (5, 1) (4, 1) (7, 1) (8, 1) (6, 5) (8, 2) (2, 1) (1, 3) (3, 7) (4, 5)

Check accessibility for a node by checking its -1 demand

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

-1

Supply up to 12 units

Cannot receive supply

ÎNO accessibility

,QWHJHU3URJUDPIRU

0XOWL

7HDPEDVHGRQ

0XOWLFRPPRGLW\)ORZ

17 0 , 0

( ) ( )

Min (1 )

e p

T T

loop a at at i it t a AA t i N

tail ahead a

D y y D v

 ‰ 

¦ ¦

¦¦

, , ( ) ( ) 0, , 1

e p e p

at at a A A a A A tail aS head aS

x x N t T

 ‰  ‰

d }

¦

¦

, , ( ) ( )

, 0, ,

e p e p

at at it a A A a AA tail ai head ai

x x v i N t T

 ‰  ‰

 }

¦

¦

0dxatd(N1)zat a A tp, }0, ,T

(2) (1)

(3)

(4)

, 0, , at at e p y dz  ‰a A A t }T

( ) , 0, , at tail a t e p y dv  ‰a A A t }T

1 , 0, ,

at at p y y d a A t }T

{ , 1}

1 1, , , 0, , a

p min T t P

aur a A u t

r R t T

D

 d  } }

¦ ¦

( ) 1 , 0, , at tail a t at e p y tv z  ‰a A A t }T

(6) (5) (7) (8) (9) 0 1

0 , 0, ,

t R

at aur p u r

z

¦¦

D d a A t }T 1 0 0 a P at p t

z a A



¦

1 1 0 0 a P R atr p r t a A D 

¦¦

(10) (11) (12)

Better than

_&

, still not good enough

Tried adding new

valid inequalities

but still

time consuming

Sequential Segment Heuristic (

SSH

)

19 S C G H I J K L F E D A B (5, 3) (3, 4) (2, 1) (4, 2) (7, 6) (4, 2) (3, 1) (8, 1) (5, 1) (4, 1) (7, 1) (8, 1) (6, 5) (8, 2) (2, 1) _{(1, 3)}

(3, 7) (4, 5) 3DUWLWLRQWKHSODQQLQJKRUL]RQLQWRVPDOOHUVHJPHQW 6ROYHVPDOOHUSUREOHPVE\ IL[WKHUHVXOWDQGJRRQ

Greedy Algorithms

20

Select arc by its weight (e.g., D

ij

/P

ij

in decreasing order)

S C G H I J K L F E D A B (5, 0) (3, 0) (2, 0) (4, 0) (7, 6) (4, 2) (3, 1) (8, 0) (5, 0) (4, 0) (7, 0) (8, 0) (6, 5) (8, 2) (1, 3) (3, 7) (4, 5) S C G H I J K L F E D A B (5, 0) (3, 0) (2, 0) (7, 6) (4, 2) (3, 1) (8, 0) (5, 0) (4, 0) (7, 0) (8, 0) (6, 5) (8, 2) (1, 3) (3, 7) (4, 5) *UHHG\7UHH*7 *UHHG\&RQQHFWHG&RPSRQHQW*&&

&RPSXWDWLRQDO([SHULPHQWV

•

(QYLURQPHQWVHWWLQJV

–

3&ZLWK8%8178LQWHO&RUHL*+]

3URFHVVRU*%5$0

–

,3E\

*XUREL

VROYHGXSWR

KU

DWPRVW

–

$OJRULWKPVE\

&&

•

3UREOHPVHWWLQJV

–

WHDPV

–

7UHH

JUDSKV

,PSURYHPHQWE\9DOLG,QHTXDOLWLHV

• Add 4 valid inequalities

• Performance of different combinations:

22

, ( )

, , 0, , e p

at i it a A A

head a i

y IND v i N i S t T

 ‰

¦

d ˜  z }

1 , 0, , 1

at at p

z dz a A t } T

1 , 0, , 1

at at e p

y dy  ‰a A A t } T

1 , 0, , 1

it it

v dv i N t } T

(13)

(14) (15) (16) (13): if a perfect arc a connects to an accessible node,

then a is also accessible.

3HUIRUPDQFH&RPSDULVRQV

• Tree graphs

• General graphs

23

&RQFOXVLRQV

• Restore damaged pipelines ASAP are

important to the QoL for refugee

• Pipeline arc restoration problem is a special

RCPSP

with

network structure

• Propose a

network compacting

scheme

• Propose exact IP models (

,

_&

,

)

Advancement of mathematical model of disaster prevention and evacuation

planning toward social implementation

November 30-December 1, 2017, Fukuoka, JAPAN

Airspace Evacuation Strategies

Maristany

de

las

Casas,

Pedro

Airspace Evacuation Strategies

Ralf Borndörfer, Christoph Grafe, Pedro M. Casas 01.12.2017

Zuse Institute Berlin

1

Zuse Institute Berlin http://www.zib.de

Description

Interdisciplinary research institute for applied mathematics and high-performance computing. Cooperations with academia and industry.

Research Units

- Numerical Analysis and Simulation - Visualization and Data Analysis - Optimization

- Scientific Information Systems - High Performance Computing - Computer Science Research 2

Intro

Yellow Ribbon Operation

4

When Airspaces Need to be Emptied

5

Intro

Flows Over Time or Dynamic Flows

(1/2) (2/1) (2/1) (2/2)

(1/1) (2/1) (1/1)

A B

C

U

V

T

Labels:(τa,ua)

6

Intro

Input and Problem Classes

Dynamic Network

A dynamic Network...

N= (D= (V,A), τ,u,S,T)

consists of

•a directed graphD= (V,A) •a transit time function

τ:A→N

•a capacity functionu:A→N •a set of sourcesS ⊂V

•a set of targetsT ⊂V

(1/1) (2/1) (1/2)

s1 s2

t1 t2

Problem Classes on Dynamic Networks

Given a networkN:= (D:= (V,A), τ,u,S,T)

Problem Extra Input Objective Evacuation

Max Flow Time limit_T MaxS − T flow

untilT −

Feasible

d-Transshipment

T, Demands d:S ∪ T →Z

d-Flow

untilT? −

Quickest

d-Transshipment

Demands d:S ∪ T →Z

Quickest

d-Flow +

8

Problem Classes

Dynamic Max-Flow

Topic Review – Dynamic Maximum Flow

1958 1959 1962 1973 1994 2002 2004 2007 2009 2011 2017 Ford and Fulkerson

Dyn. Max Flow Introduction

Example: Dynamic Max-Flow Problem

Given a networkN= (D= (V,A), τ,u,S,T)and a time limitT, a dynamicmax-flow problem

seeks to maximize the flow fromStoT inN withinTunit of time.

(1/1) (2/1)

(1/2)

s1 s2

t1 t2

θ

Inflow(t1+t2)

11

Labels:(τa,ua),T=4,θ=4

10

Dynamic Max-Flow Formulation

Time Dependent Max-Flow

max

a∈δ+(s)

θ∈{0,...,T}

xa(θ)

s.t.

a∈δ+(v)

xa(θ) =

a∈δ−(v)

xa(θ), ∀v∈V\{s.t}, θ∈[T]

xa(θ)≤ca, ∀a∈A, θ∈[T]

xa(θ)∈N, ∀a∈A, θ∈[T]

11

Algorithms for Dynamic Max-Flow

Static Max-Flow on Time Expanded Network + Easy to understand and implement

– Size of Time Expanded Network not polynomial

+ Time Expanded Network can be manipulated in applications

→Pseudo-Polynomial algorithm depending onT. Temporarily Repeated Flow [Ford & Fulkerson 62]

Time Expanded Network

For a networkN= (D= (V,A), τ,u,S,T)and time limitT

Original Network

(1/1) (2/1) (1/2)

s1 s2

t1 t2

Labels:(τa,ua)

Time Expanded NetworkT=2

s2 t2 s1 t1

13

Problem Classes

Feasible Dynamic Transshipment

Problem

Problem Classes on Dynamic Networks

Given a networkN= (D= (V,A), τ,u,S,T)

Problem Extra Input Objective Evacuation

Max Flow Time limit_T MaxS − T flow

untilT −

Feasible

d-Transshipment

T, Demands d:S ∪ T →Z

d-Flow

untilT? −

Quickest

d-Transshipment

Demands d:S ∪ T →Z

Quickest

Example Dynamic Transshipment Problem

Given a networkN= (D= (V,A), τ,u,S,T), a demand function

d:S ∪ T →Z, and an time limitT, a dynamictransshipment problem

seeks to find a flow inNthat satisfiesdin at mostTtime units.

(1/1) (2/1)

(1/2)

s1 s2

t1 t2

θ

Inflow(t1+t2)

4

Labels:(τa,ua),d(si) =2,d(ti) =−2,T=3,θ=3

15

Dyn. Transshipment Feasibility via Dynamic Max-Flow

Graph transformation for an instance I of the Dynamic Transshipment Problem

(1/1) (2/1) (1/2)

(0/2) (0/2)

(0/2) (0/2)

s1 s2

t1 t2

s t

Labels:(τa,ua),d(si) =2,d(ti) =−2,T=3

Iis feasible iff

maxFlow(s,t,T)≥

s∈S

d(s)

16

Problem Classes

Topic Review – Quickest Transshipment

1958 1959 1962 1973 1994 2002 2004 2007 2009 2011 2017 Ford and Fulkerson

Dyn. Max Flow Introduction

F&F - Dyn. Max Flow strongly poly.

Hoppe & Tardos Quickest Transsh. strongly poly.

17

Quickest Transshipment via Dynamic Max-Flow

Graph transformation for an instance I of the Dynamic Transshipment Problem

(1/1) (2/1) (1/2)

(0/2) (0/2)

(0/2) (0/2)

s1 s2

t1 t2

s t

Labels:(τa,ua),d(si) =2,d(ti) =−2

Binary Search onT

SetU=bigM,L=0,T=bigM/2 and run a binary search untilTis the smallest value s.t.maxFlow(s,t,T)is feasible.

18

Algorithms For Quickest Transshipment

Binary Search Algorithm

+ Easy to understand and implement

+ Uses time expanded network→customizable modeling - Uses time expanded network→pseudo polynomial running time

Submodular Function min. and Lexicographically Maximum Flows [Hoppe, Tardos 94]

Evacuation

Earliest Arrival Transshipments

Topic Review – Earliest Arrival Transshipment

1958 1959 1962 1973 1994 2002 2004 2007 2009 2011 2017 Ford and Fulkerson

Dyn. Max Flow Introduction

F&F - Dyn. Max Flow strongly poly.

Gale SS-ST Earliest Arrivals Existence

Minieka

Pseudo Poly. Algo for Earliest Arrival Fl. Richardson & Tardos Pseudo Poly. Algo for Earliest Arrival Tr.

Klinz - Dyn MCFN P-hard

Skutella, EAT inO(in+out)

Hoppe & Tardos Quickest Transsh. strongly poly.

20

Earliest Arrival Transshipment

Given a networkN= (D= (V,A), τ,u,S,T)and demands

d:S × T →R

Different evacuation scenarios

mintime needed to send all supplies tot (2)

maxamount of flow enteringtat everyθ∈[T] (3) Optimization Problems for Evacuation

•Optimizing objective (2) we get aQuickest Transshipment

Example: Quickest Transshipment vs. Earliest Arrival

θ

Inflow(T, θ)

Earliest Arrival,Quickest Transshipment

22

Existence of Earliest Arrival Flows

Given a networkN= (D= (V,A), τ,u,S,T)and demands

d:S × T →R

Do Earliest Arrival Flows always exist?

•If flow hurries towards the correct sink, yes.

•This can only be ensured if|T |=1.

Theorem [Minieka73]

Earliest arrival flows always exist if there is only one sink.

24

Existence of Earliest Arrival Flows – The MultiSink Case

Example: The graphD1with unit transit times

(1) (1) (1)

s1 s2

t1 t2

Labels:ua,d(si) =2,d(ti) =−2

Quickest Transshipment

θ 1 2 1+2 Inflowt1 1 1 2

Inflowt2 1 1 2

InflowT 2 2 4

Earliest Arrival?

θ 1 2 1+2 Inflowt1 2 0 2

Inflowt2 1 0 1

Existence of Earliest Arrival Flows – The MultiSink Case

(1) (1) (1)

s1 s2

t1 t2

GraphD1

(2) (1)

(2)

u v w

x

GraphD2,d(u) =4,d(w) =

2,d(v) =−2,d(x) =−4

Theorem [Schmidt, Skutella 2010]

A networkN allows for an Earliest Arrival Transshipment for all choices of capacities and balances iff the graphDdoes not containD1orD2as

subgraphs.

26

Existence of Earliest Arrival Flows – The MultiSink Case

In practice, many multiSink applications can be reformulated.

(1) (1) (1)

(d(t2))

(d(t1))

s1 s2

t1 t2

t

GraphD1

Theorem [Richardson, Tardos 2002]

A networkN with multiple sources and a single sink allows for an Earliest Arrival Transshipment for all choices of capacities and balances.

27

Algorithms for Earliest Arrival

Given a networkN= (D= (V,A), τ,u,S,t)and demands

d:{S,t} →R Successive Shortest Path Algorithm

1: Initialize flow_x=0 on time exp. network with_Tbig enough 2: whiles,tconnected in the residual networkRexp

N do

3: Augment_xalong shortest_(s,t)-path inRexp

N

4: end while

5: Use gen. path decomposition of Step 3 and temporarily repeat to get dynamic flowxθ.

6: if _xθsatisfies_dthen 7: return Success

8: else

Flows with Bridge Capacities

Problem Description

Flows with Bridge Capacities

Consider a networkN= (D= (V,A), τ,u,S,T)and demands

d:S × T →R

with new type of capacities ba:

θ+τa−1

i=θ

xa(i)≤ba, a∈A, θ∈ {0, . . . ,T}

Classical Capacities

θ

xa

ua

1 2 3

Arcahas capacityua=3 29

Flows with Bridge Capacities

Consider a networkN= (D= (V,A), τ,u,S,T)and demands

d:S × T →R

with new type of capacities ba:

θ+τa−1

i=θ

xa(i)≤ba, a∈A, θ∈ {0, . . . ,T}

Classical Capacities

θ

xa

ua

1 2 3

Bridge Capacities

θ

xa

ua

Topic Review – Bridge Capacities

1958 1959 1962 1973 1994 2002 2004 2007 2009 2011 2017 Ford and Fulkerson

Dyn. Max Flow Introduction

F&F - Dyn. Max Flow strongly poly.

Gale SS-ST Earliest Arrivals Existence

Minieka

Pseudo Poly. Algo for Earliest Arrival Fl. Richardson & Tardos Pseudo Poly. Algo for Earliest Arrival Tr.

Klinz - Dyn MCFN P-hard

Skutella, EAT inO(in+out)

Melkonian Bridge Capacities Intro & weaklyN P-compl.

Skutella - FPTAS for Bridge Cap.

Hamacher Integer Bridge stronglyN P-compl Hoppe & Tardos

Quickest Transsh. strongly poly.

30

Flows with Bridge Capacities – Model

Integer Bridge Problem

max

a∈δ+₍s)

θ∈{0,...,T}

xa(θ)

s.t.

a∈δ+₍v)

xa(θ) =

a∈δ−(v)

xa(θ), ∀v∈V\{s.t},∀θ∈ {1, . . . ,T}

θ+τa−1

i=θ

xa(i)≤ua, ∀a∈A,∀θ∈ {1, . . . ,T}

xa(θ)∈N, ∀a∈A,∀θ∈ {1, . . . ,T}

LP-Relaxation no longer feasible!

Note that the bridge constraints destroy total unimodularity!

31

Airspace Evacuation

Input – The Airway Network

32

Input – Sources, Sinks and Arc Capacities

Sources and Sinks

•Sources: The position (nodes) of a given set of aircraft.

•Sinks: Available airports in the Airway Network (graph).

Arc Capacities

Common arcs have capacity 1 to simulate waiting.

33

Immediate Start and Airport Capacity

Immediate Start

Aircraft can’t wait at a node.

•Single copy of airports/sources needed.

•Only one unit of flow per source!

Airport Capacity and Multiple Sinks?

•No need for multiple sinks: An airportdoes not demandaircraft.

•BUT it can store amaximum number of aircraft

35

Airspace Evacuation

A Graph-Based Algorithm

A Graph-Based Algorithm

Graph Preprocessing

•Time Expansion needed

•Time Expansion does little harm (only one copy of each source and no waiting arcs)

A Graph-Based Algorithm

Graph Preprocessing

•Time Expansion needed

•Time Expansion does little harm (only one copy of each source and no waiting arcs)

•Airport Filters needed (Airport capacities→Bridges)

Run

AdaptedSuccessive Shortest Path Algorithm

36

Time Expansion for Airspace Evacuation

Consider the following instances: japan_200_20 and europe_200_20

Japan Europe

Original number of nodes 13,978 23,103 Original number of arcs 22,521 102,502

Chosen time limitT[min] 596 550

Nodes after time exp. 1,277,716 8,053,503 Arcs after time exp. 5,267,948 57,884,410

37

Airport Filters

Original graph

t cap=10

Airport Filter in Time Expanded Network

(10)

t1 t2 tT

θ=1

θ=2

θ=T